package leetcode_day._2021._202104._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/14 9:40
 * 实现 Trie (前缀树)
 * 算法：前缀树  字典树
 * 使用场景：自动补完和拼写检查
 * 思路：
 *   多叉树
 *   每个节点的 children 是长度为 26 的数组
 *
 */
public class _14_208 {
}
//class Trie {
//    List<String> trie;
//
//    /** Initialize your data structure here. */
//    public Trie() {
//        trie = new ArrayList<>();
//    }
//
//    /** Inserts a word into the trie. */
//    public void insert(String word) {
//        trie.add(word);
//    }
//
//    /** Returns if the word is in the trie. */
//    public boolean search(String word) {
//        for (String s : trie) {
//            if (word.equals(s)) return true;
//        }
//        return false;
//    }
//
//    /** Returns if there is any word in the trie that starts with the given prefix. */
//    public boolean startsWith(String prefix) {
//        for (String s : trie) {
//            int len = Math.min(s.length(), prefix.length());
//            if (prefix.equals(s.substring(0, len))) return true;
//        }
//        return false;
//    }
//}

class Trie {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
    }
    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            int len = word.charAt(i) - 'a';
            if (null == cur.children[len]) cur.children[len] = new TrieNode();
            cur = cur.children[len];
        }
        cur.isWord = true;
    }

    // 最后一个节点的 isWord 为 true
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            cur = cur.children[word.charAt(i) - 'a'];
            if (null == cur) return false;
        }
        return cur.isWord;
    }

    // 节点不为空，能够把字符串循环完
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            cur = cur.children[prefix.charAt(i) - 'a'];
            if (null == cur) return false;
        }
        return true;
    }
}
